递归和动态规划——换钱的方法数

Posted on | In ,

题目：给定数组arr，所有值都为正且不重复。每个值代表一种货币，每种货币可以使用任意张，给定一个整数aim，求换钱有多少种方法。
arr = {5, 10, 25, 1}，aim=15，组成15的方法有6种。

分析：暴力递归，记忆搜索，动态规划。
实现：动态规划建立 M*（aim+1)的二维数组dp，dp[i][j]为在使用货币arr[0,..i]的情况下，组成钱数j的方法有多少种。

  1. 对于第一列，表示aim=0时，有多少种货币组成方法，即不使用任何货币，dp[j][0]=1。
  2. 对于第一行，表示只能使用arr[0]的情况下，组成钱数j的方法，如arr[0]=5,只有在j=5，10,15，..等arr[0]的倍数的地方有1种方法。令dp[0][k*arr[0]]=1,其中0<=k*arr[0]<=aim。
  3. 对于dp矩阵的非第一行第一列，在位置（i，j），dp[i][j]的值是以下情况下几个值的累加：
    1）完全不使用arr[i]货币，只使用arr[0，…i-1]货币，方法数为dp[i-1][j]。
    2）使用1张arr[i]货币，剩下的用arr[0,…i-1]货币，方法数为dp[i-1][j-arr[i]];（表示在使用1张arr[i]的情况下，组成钱数j-arr[i]的方法数。从钱数j-arr[i]到钱数j只用一种方法，那就是加上1张arr[i]，所以说方法数没有变，dp[i][j]=dp[i-1][j-arr[i]]，使用k张就等于使用1张arr[i]的方法数。（可以类比第0行，只要是arr[0]的倍数的地方，都只有一种方法，方法数没变））
    3）使用2张arr[i]货币，剩下的用arr[0,..i-1]货币，方法数为dp[i-1][j-2*arr[i]]；
    …
    k+1）使用k张arr[i]货币，剩下的用arr[0,..i-1]货币，方法数为dp[i-1][j-k*arr[i]]，其中j-k*arr[i]>=0。
    所以步骤3的最终结果为：
    dp[i][j]=dp[i-1][j-k*arr[i]],j-k*arr[i]>=0。（其中k=0表示不使用任何arr[i])
    最后dp[M-1][aim]（即矩阵的右下角元素）就是最终结果。

在最差的情况下，对位置（i,j）来说，需要枚举dp[i-1][0,..j]上所有的值，dp一共有M*aim个位置，因此总时间复杂度为O（M*aim^2）。

动态规划进阶：时间复杂度为O（M*aim）
上面步骤3中的2）到k+1）过程，它们其实就是dp[i-1][j-arr[i]]的值（使用k张就等于使用1张arr[i]的方法数），因此可以将步骤3化简为：
dp[i][j]=dp[i-1][j]+dp[i-1][j-arr[i]]，其中j>arr[i]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Coins {
	/**
	 * 计算组成钱数aim的方法数。时间复杂度为O（M*aim^2）
	 * @param arr 存币值的数组，为正数且不重复
	 * @param aim 需要组成的钱数
	 * @return 组成钱数的方法数
	 */
	public int coins(int[] arr, int aim) {
		if (arr == null || arr.length == 0 || aim < 0) {
			return 0;
		}
		int m = arr.length;
		int n = aim + 1;
		int[][] dp = new int[m][n];
		//对第一列赋值，全为1
		for (int i = 0; i < m; i++) { 
			dp[i][0] = 1;
		}
		//对第一行赋值,在arr[0]的整数倍处（j < aim / arr[0]）为1
		for(int j = 1; arr[0] * j < aim; j++) {
			dp[0][arr[0] * j] = 1;
		}
		//将dp中的所有元素相加 
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				for (int k = 0; j - k * arr[i] >= 0; k++) {
					dp[i][j] += dp[i - 1][j - k * arr[i]]; //其中k=0表示不使用任何arr[i] 
				}
			}
		}
		return dp[m-1][n-1];
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 对上边的动态规划进一步化简
 * 时间复杂度为O（M*aim）
 * @param arr
 * @param aim
 * @return
 */
public int coins2(int[] arr, int aim) {
	if (arr == null || arr.length == 0 || aim < 0) {
		return 0;
	}
	int m = arr.length;
	int n = aim + 1;
	int[][] dp = new int[m][n];
	//对第一列赋值，全为1
	for (int i = 0; i < m; i++) { 
		dp[i][0] = 1;
	}
	//对第一行赋值，在arr[0]的整数倍处（j < aim / arr[0]）为1
	for(int j = 1; arr[0] * j < aim; j++) {
		dp[0][arr[0] * j] = 1;
	}
	//将dp中的所有元素相加 
	for (int i = 1; i < m; i++) {
		for (int j = 1; j < n; j++) {
			dp[i][j] = dp[i-1][j]; //上面部分的值
			dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0; //再加上左边部分的值，对j-arr[i]作判定。
		}
	}
	return dp[m-1][n-1];
}
1
2
3
4
5
6
7
8
	//Test
	public static void main(String[] args) {
		Coins  c = new Coins();
		int[] arr = {5, 10, 25, 1};
		int aim = 15;
		System.out.println(c.coins(arr, aim));	
	}
}